package com.peng.leetcode.unionFind;

import java.util.ArrayList;
import java.util.List;

/**
 * RegionsBySlashes
 * 959. 由斜杠划分区域
 *
 * @author: lupeng6
 * @create: 2021/1/25 14:44
 */
public class RegionsBySlashes {

    public static void main(String[] args) {
        String[] strings = {
                "\\/",
                "/\\"
        };
        int i = new RegionsBySlashes().regionsBySlashes(strings);
        System.out.println(i);
    }

    /**
     * 并查集计算
     *
     * @author lupeng6
     * @date 2021/1/25 14:45
     */
    public int regionsBySlashes(String[] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int length = grid.length;
        // 转换为 一维
        int size = 4 * length * length;
        UnionFind unionFind = new UnionFind(size);
        for (int i = 0; i < grid.length; i++) {
            String row = grid[i];
            char[] chars = row.toCharArray();
            for (int j = 0; j < chars.length; j++) {
                int index = 4 * (i * length + j);
                char ch = chars[j];
                if (ch == '/') {
                    // 合并0 -> 3, 1 -> 2
                    unionFind.union(index, index + 3);
                    unionFind.union(index + 1, index + 2);
                } else if (ch == '\\') {
                    // 合并0 -> 1, 2 -> 3
                    unionFind.union(index, index + 1);
                    unionFind.union(index + 2, index + 3);
                } else {
                    // 合并 0 -> 1, 1 -> 2, 2 -> 3
                    unionFind.union(index, index + 1);
                    unionFind.union(index + 1, index + 2);
                    unionFind.union(index + 2, index + 3);
                }

                // 合并相邻的单元格, curr1 -> next3, curr2 -> nextRow0
                if (j + 1 < length) {
                    unionFind.union(index + 1, 4 * (i * length + j + 1) + 3);
                }
                if (i + 1 < length) {
                    unionFind.union(index + 2, 4 * ((i + 1) * length + j));
                }
            }
        }
        return unionFind.count;
    }

    static class UnionFind {
        private List<Integer> parent;

        private int count;

        public UnionFind(int size) {
            this.count = size;
            this.parent = new ArrayList<>(size);
            for (int i = 0; i < size; i++) {
                parent.add(i);
            }
        }

        public int find(int x) {
            if (x != parent.get(x)) {
                parent.set(x, find(parent.get(x)));
                x = parent.get(x);
            }
            return x;
        }

        public void union(int x, int y) {
            int xRoot = find(x);
            int yRoot = find(y);
            if (xRoot != yRoot) {
                parent.set(xRoot, yRoot);
                count--;
            }
        }
    }

}
